package dRegAut.opg2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Nondeterministic finite state automaton with &Lambda; transitions.
 * [Martin, Th. 3.12]
 *
 * @author Michael B. Mogensen
 */
public class NFA implements Cloneable {

    /**
     * Our representation of &Lambda;.
     */
    public static final char LAMBDA = Character.MAX_VALUE;

    /**
     * Set of {@link State} objects (Q).
     */
    public Set<State> states;

    /**
     * The automaton alphabet (&Sigma;).
     */
    public Alphabet alphabet;

    /**
     * Initial state (q<sub>0</sub>). Member of {@link #states}.
     */
    public State initial;

    /**
     * Accept states (A). Subset of {@link #states}.
     */
    public Set<State> accept;

    /**
     * Transition function (&delta;).
     * This is a map from pairs of states and alphabet symbols to sets of states
     * (&delta;:
     * Q<img src="http://cs.au.dk/~amoeller/dRegAut/times.gif"
     *      alt="x">(<img src="http://cs.au.dk/~amoeller/dRegAut/Sigma.gif"
     *      alt="sigma"><img src="http://cs.au.dk/~amoeller/dRegAut/union.gif"
     *      alt="union">{&Lambda;})
     * <img src="http://cs.au.dk/~amoeller/dRegAut/rightarrow.gif" alt="-&gt;"> 2<sup>Q</sup>).
     * We represent &Lambda; by {@link #LAMBDA}.
     */
    public Map<StateSymbolPair,Set<State>> transitions;

    /**
     * Checks that this automaton is well-defined.
     * This method should be invoked after each <tt>NFA</tt> operation during testing.
     * @return this automaton
     * @exception AutomatonNotWellDefinedException if this automaton is not well-defined
     */
    public NFA checkWellDefined() throws AutomatonNotWellDefinedException {
        if (states==null || alphabet==null || alphabet.symbols==null ||
            initial==null || accept==null || transitions==null) {
            throw new AutomatonNotWellDefinedException("invalid null pointer");
        }
        if (!states.contains(initial)) {
            throw new AutomatonNotWellDefinedException("the initial state is not in the state set");
        }
        if (!states.containsAll(accept)) {
            throw new AutomatonNotWellDefinedException("not all accept states are in the state set");
        }
        for (State s : states) {
            ArrayList<Character> extended_symbols = new ArrayList<Character>(alphabet.symbols);
            extended_symbols.add(LAMBDA);
            for (char c : extended_symbols) {
                Set<State> ps = transitions.get(new StateSymbolPair(s, c));
                if (ps!=null) {
                    for (State s2 : ps) {
                        if (!states.contains(s2)) {
                            throw new AutomatonNotWellDefinedException("there is a transition to a state that is not in state set");
                        }
                    }
                }
            }
        }
        for (StateSymbolPair sp : transitions.keySet()) {
            if (!states.contains(sp.state)) {
                throw new AutomatonNotWellDefinedException("transitions refer to a state not in the state set");
            }
            if (sp.symbol!=LAMBDA && !alphabet.symbols.contains(sp.symbol)) {
                throw new AutomatonNotWellDefinedException("non-alphabet symbol appears in transitions");
            }
        }
        return this;
    }

    /**
     * Constructs an uninitialized NFA.
     * <tt>states</tt> and <tt>accept</tt> are set to empty sets,
     * <tt>transitions</tt> is set to an empty map.
     */
    public NFA() {
        states = new HashSet<State>();
        accept = new HashSet<State>();
        transitions = new HashMap<StateSymbolPair,Set<State>>();
    }

    /**
     * Clones this automaton.
     */
    @Override
    public Object clone() {
        NFA f;
        try {
            f = (NFA) super.clone(); // always clone using super.clone()
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException(e);
        }
        f.states = new HashSet<State>();
        f.accept = new HashSet<State>();
        f.transitions = new HashMap<StateSymbolPair,Set<State>>();
        Map<State,State> m = new HashMap<State,State>(); // map from old states to new states
        for (State p : states) {
            State s = (State) p.clone();
            f.states.add(s);
            m.put(p, s);
            if (accept.contains(p)) {
                f.accept.add(s);
            }
        }
        f.initial = m.get(initial);
        for (Map.Entry<StateSymbolPair,Set<State>> e : transitions.entrySet()) {
            StateSymbolPair ssp = e.getKey();
            Set<State> set = e.getValue();
            Set<State> ns = new HashSet<State>();
            for (State q : set) {
                ns.add(m.get(q));
            }
            f.transitions.put(new StateSymbolPair(m.get(ssp.state), ssp.symbol), ns);
        }
        return f;
    }

    /**
     * Constructs a new NFA that accepts the empty language. [Martin, Th. 3.25]
     *
     * @param a automaton alphabet
     */
    public static NFA makeEmptyLanguage(Alphabet a) {
        // TODO Martin, Th. 3.25

        // The NFA is created as makeEmptyString, but without any accepted states
        NFA result = NFA.makeEmptyString(a);
        result.accept.clear();

        return result;
    }

    /**
     * Constructs a new NFA that accepts the language containing only the empty
     * string.
     *
     * @param a automaton alphabet
     */
    public static NFA makeEmptyString(Alphabet a) {
        NFA f = new NFA();
        f.alphabet = a;
        State s = new State();
        f.states.add(s);
        f.initial = s;
        f.accept.add(s);
        return f;
    }

    /**
     * Constructs a new NFA that accepts the language containing only the given
     * singleton string. [Martin, Th. 3.25]
     *
     * @param a automaton alphabet
     * @param c the symbol in the singleton string
     */
    public static NFA makeSingleton(Alphabet a, char c) {
        // TODO Martin, Th. 3.25 page 111

        // Rely on makeEmptyString(a) without the accepted states.
        NFA result = NFA.makeEmptyString(a);
        result.accept.clear();

        // Empty-string-NFA is extended with transition to a state accepting character c
        State acceptSingletonSymbonState = new State("Accept " + c);
        StateSymbolPair ssp = new StateSymbolPair(result.initial, c);

        // Add transition from initial state to accepting state
        Set<State> tempSet = new HashSet<State>();
        tempSet.add(acceptSingletonSymbonState);
        result.transitions.put(ssp, tempSet);
        result.accept.add(acceptSingletonSymbonState);

        return result;
    }

    /**
     * Returns <a href="http://www.graphviz.org/" target="_top">Graphviz Dot</a>
     * representation of this automaton.
     * (To convert a dot file to postscript, run '<tt>dot -Tps -o file.ps file.dot</tt>'.)
     * Lambdas are written as '<tt>%</tt>'.
     */
    public String toDot() {
        StringBuffer b = new StringBuffer("digraph Automaton {\n");
        b.append("  rankdir = LR;\n");
        Map<State,Integer> id = new HashMap<State,Integer>();
        for (State s : states) {
            id.put(s, Integer.valueOf(id.size()));
        }
        for (State s : states) {
            b.append("  ").append(id.get(s));
            if (accept.contains(s)) {
                b.append(" [shape=doublecircle,label=\""+s.name+"\"];\n");
            } else {
                b.append(" [shape=circle,label=\""+s.name+"\"];\n");
            }
            if (s==initial) {
                b.append("  in [shape=plaintext,label=\"\"];\n");
                b.append("  in -> ").append(id.get(s)).append(";\n");
            }
        }
        for (Map.Entry<StateSymbolPair,Set<State>> e : transitions.entrySet()) {
            StateSymbolPair ssp = e.getKey();
            Set<State> set = e.getValue();
            for (State q : set) {
                b.append("  ").append(id.get(ssp.state)).append(" -> ").append(id.get(q));
                b.append(" [label=\"");
                if (ssp.symbol==LAMBDA) {
                    b.append('%');
                } else {
                    char c = ssp.symbol.charValue();
                    if (c>=0x21 && c<=0x7e && c!='\\' && c!='%') {
                        b.append(c);
                    } else {
                        b.append("\\u");
                        String s = Integer.toHexString(c);
                        if (c<0x10) {
                            b.append("000").append(s);
                        } else if (c<0x100) {
                            b.append("00").append(s);
                        } else if (c<0x1000) {
                            b.append("0").append(s);
                        } else {
                            b.append(s);
                        }
                    }
                }
                b.append("\"];\n");
            }
        }
        return b.append("}\n").toString();
    }

    /**
     * Returns number of states in this automaton.
     */
    public int getNumberOfStates() {
        return states.size();
    }

    /**
     * Looks up transitions in transition function.
     *
     * @return &delta;(q,c)
     * @exception IllegalArgumentException if <tt>c</tt> is not in the alphabet
     */
    public Set<State> delta(State q, char c) throws IllegalArgumentException {
        if (!alphabet.symbols.contains(c) && c != LAMBDA) {
            throw new IllegalArgumentException("symbol '" + c + "' not in alphabet");
        }

        Set<State> set = transitions.get(new StateSymbolPair(q, c));
        if (set == null) {
            set = new HashSet<State>();
        }
        return set;
    }

    /**
     * Computes the &Lambda;-closure of the given state set. [Martin, Def. 3.13]
     *
     * @param set set of {@link State} objects
     * @return set of {@link State} objects (the input set is unmodified)
     */
    public Set<State> lambdaClosure(Set<State> set) {
        // contains the states that are in the closure and have been visited
        Set<State> res = new HashSet<State>();

        // contains the states that are in the closure but have not yet been visited
        Set<State> pending = new HashSet<State>();
        pending.addAll(set);

        while (!pending.isEmpty()) {
            State q = pending.iterator().next();
            pending.remove(q);

            // Lambda closure on initial states always includes it self (slide 23)
            res.add(q);
            Set<State> s = new HashSet<State>(delta(q, LAMBDA));
            // avoid doublets in result
            s.removeAll(res);
            // Add delta result to pending
            pending.addAll(s);
        }

        return res;
    }

    /**
     * Performs transitions in extended transition function. [Martin, Def. 3.14]
     *
     * @return &delta;*(q,s)
     * @exception IllegalArgumentException if a symbol in <tt>s</tt> is not in the alphabet
     */
    public Set<State> deltaStar(State q, String s) throws IllegalArgumentException {
        // Slide 22
        Set<State> set = new HashSet<State>();
        set.add(q);
        // Initialize to lambda closure, which as minimum includes q it self
        set = lambdaClosure(set);

        // Handle each character in the transition string
        for (char c : s.toCharArray()) {
            Set<State> nset = new HashSet<State>();

            for (State p : set) {
                // The great union of delta states
                nset.addAll(delta(p, c));
            }
            set = lambdaClosure(nset);
        }

        return set;
    }

    /**
     * Runs the given string on this automaton. [Martin, Def. 3.14]
     *
     * @param s a string
     * @return true if the string is accepted
     * @exception IllegalArgumentException if a symbol in <tt>s</tt> is not in
     *                the alphabet
     */
    public boolean accepts(String s) throws IllegalArgumentException {
        Set<State> set = deltaStar(initial, s);
        // RetainAll (intersection of the two sets)
        set.retainAll(accept);

        return !set.isEmpty();
    }

    /**
     * Adds a &Lambda; transition.
     * @param p from state
     * @param q to state
     */
    public void addLambda(State p, State q) {
        StateSymbolPair ssp = new StateSymbolPair(p, LAMBDA);
        Set<State> s = transitions.get(ssp);
        if (s==null) {
            s = new HashSet<State>();
            transitions.put(ssp, s);
        }
        s.add(q);
    }

    /**
     * Constructs a new automaton whose language is the union of the language of
     * this automaton and the language of the given automaton. [Martin, Th.
     * 3.25] The input automata are unmodified.
     *
     * @exception IllegalArgumentException if the alphabets of <tt>f</tt> and
     *                this automaton are not the same
     */
    public NFA union(NFA f) throws IllegalArgumentException {
        // TODO Martin, Th. 3.25

        // 1: All states (normal+accepted) from NFA 1 and 2 are states of the new NFA
        // 2: All transitions from NFA 1 and 2 are transitions of the new NFA
        // 3: Add new initial transition state (add to states)
        // 4: Add lambda transitions from new initial state to both initial states of NFA 1 and NFA 2
        // 5: Accepted states are union - all from both NFAs

        NFA thisNFA = (NFA) this.clone();
        NFA fNFA = (NFA) f.clone();

        NFA result = new NFA();
        result.states.addAll(thisNFA.states);
        result.states.addAll(fNFA.states);
        result.accept.addAll(thisNFA.accept);
        result.accept.addAll(fNFA.accept);

        result.transitions.putAll(thisNFA.transitions);
        result.transitions.putAll(fNFA.transitions);

        result.initial = new State("UnionInitialState");
        result.states.add(result.initial);
        result.addLambda(result.initial, thisNFA.initial);
        result.addLambda(result.initial, fNFA.initial);

        return result;
    }

    /**
     * Constructs a new automaton whose language is the concatenation of the
     * language of this automaton and the language of the given automaton.
     * [Martin, Th. 3.25] The input automata are unmodified.
     *
     * @exception IllegalArgumentException if the alphabets of <tt>f</tt> and
     *                this automaton are not the same
     */
    public NFA concat(NFA f) throws IllegalArgumentException {
        if (!alphabet.equals(f.alphabet)) {
            throw new IllegalArgumentException("alphabets are different");
        }
        NFA f1 = (NFA) this.clone();
        NFA f2 = (NFA) f.clone();
        NFA n = new NFA();
        n.alphabet = alphabet;
        n.states.addAll(f1.states);
        n.states.addAll(f2.states);
        n.accept.addAll(f2.accept);
        n.initial = f1.initial;
        n.transitions.putAll(f1.transitions);
        n.transitions.putAll(f2.transitions);

        // This NFA is concatenated by another NFA, accept states from this must now lead to (lambda transition) the
        // initial state of the other NFA. This NFAs accept states are no longer treated as accept states, only as
        // temporary states on the way to the other NFAs accept states.
        for (State s : f1.accept) {
            n.addLambda(s, f2.initial);
        }
        return n;
    }

    /**
     * Constructs a new automaton whose language is the Kleene star of the
     * language of this automaton. [Martin, Th. 3.25] The input automaton is unmodified.
     */
    public NFA kleene() {
        // TODO Martin, Th. 3.25

        // 1: Only accepting state = new initial state (qk)
        // 2: Add all states from this NFA to new NFA
        // 2: Add all transitions from this NFA to new NFA
        // 2: Add lambda transition from qk to this NFA initial state
        // 3: Add lambda transition from every accepting state in this NFA to qk

        NFA thisNFA = (NFA) this.clone();
        NFA result = new NFA();
        result.initial = new State("qk");
        result.states.add(result.initial);
        result.accept.add(result.initial);

        result.states.addAll(thisNFA.states);
        result.transitions.putAll(thisNFA.transitions);

        result.addLambda(result.initial, thisNFA.initial);
        for (State acceptState : thisNFA.accept) {
            result.addLambda(acceptState, thisNFA.initial);
        }

        return result;
    }

    /**
     * Constructs an equivalent {@link NFA} by reducing all &Lambda; transitions
     * to other transitions (and if necessary, making the initial state an
     * accept state). The input automaton is unmodified.
     */
    public NFA removeLambdas() {
        NFA f = new NFA();
        f.alphabet = alphabet;
        Map<State,State> m = new HashMap<State,State>(); // map from old states to new states
        for (State p : states) {
            State s = (State) p.clone();
            f.states.add(s);
            m.put(p, s);
            if (accept.contains(p)) {
				f.accept.add(s);
			}
        }
        f.initial = m.get(initial);
        Set<State> cl = new HashSet<State>();
        cl.add(initial);
        cl = lambdaClosure(cl);
        cl.retainAll(accept);
        if (!cl.isEmpty()) {
			f.accept.add(f.initial);
		}
        for (State p : states) {
			for (char c : alphabet.symbols) {
                Set<State> set = deltaStar(p, Character.toString(c));
                Set<State> nset = new HashSet<State>();
                for (State q : set) {
					nset.add(m.get(q));
				}
                f.transitions.put(new StateSymbolPair(m.get(p), c), nset);
            }
		}
        return f;
    }

    /**
     * Determinizes this automaton by constructing an equivalent {@link FA}.
     * [Martin, Th. 3.18] The input automaton is unmodified. This implementation
     * only constructs the reachable part of the subset state space. It first
     * calls {@link #removeLambdas()} to eliminate &Lambda; transitions.
     */
    public FA determinize() {
        // TODO Martin, Th. 3.18 page 106 (see fig 3.7 page 97 + example 3.21 page 108)
        NFA thisNFA = (NFA) this.clone();
        thisNFA.removeLambdas();

        FA newFA = new FA();
        newFA.alphabet = alphabet;
        newFA.initial = thisNFA.initial;
        newFA.states.add(thisNFA.initial);

        // States pending to be handled. The set is build up from initial state and states reachably from current state
        Set<State> statesPending = new HashSet<State>();
        statesPending.add(thisNFA.initial);

        // Contains states handled for all elements in alphabet
        Set<State> handledStates = new HashSet<State>();

        // Each new FA state added is collected here as key=new state, value=set of states combining the new state
        // The map is used for tracking states already handled
        Map<Set<State>, State> originAndState = new HashMap<Set<State>, State>();
        Map<State, Set<State>> stateAndOrigin = new HashMap<State, Set<State>>();

        State voidState = new State("Ø");

        // While not all states (still collecting) are handles
        while (!statesPending.isEmpty()) {
            State state = statesPending.iterator().next();
            statesPending.remove(state);

            for (char c : newFA.alphabet.symbols) {
                Set<State> tempStates = collectStatesFromDelta(state, c, stateAndOrigin);
                System.out.println(c + " " + state + " " + tempStates);
                State tempState = originAndState.get(tempStates);
                // If a state based on these states exists in registry it must NOT be handled fully (whole alphabet)
                State newState = null;
                if (tempState == null) {

                    if (tempStates.size() == 0) {
                        // Add link to void state
                        newState = voidState;

                    } else if (tempStates.size() == 1) {
                        // Use state as is
                        newState = tempStates.iterator().next();

                    } else if (tempStates.size() > 1) {
                        // Combine more than one states to a new state
                        String newStateName = "";
                        for (State s : tempStates) {
                            newStateName += s.name;
                        }

                        newState = new State(newStateName);
                    }

                    statesPending.add(newState);
                    // Found new (maybe combined) state for the FA
                    newFA.states.add(newState);
                    originAndState.put(tempStates, newState);
                    stateAndOrigin.put(newState, tempStates);

                    // After retainAll tempStates contains intersection of states in accept on NFA, if any the new state
                    // must be accept state
                    Set<State> retainAllResult = new HashSet<State>(tempStates);
                    retainAllResult.retainAll(thisNFA.accept);
                    if (retainAllResult.size() > 0) {
                        newFA.accept.add(newState);
                    }
                } else {
                	newState = tempState;
                }

                // Add transition from (initial state, c) to the new state
                StateSymbolPair ssp = new StateSymbolPair(state, c);
                newFA.transitions.put(ssp, newState);

                System.out.println("Adding transition=(" + ssp + "->" + newState + ")");
            }

            handledStates.add(state);
        }

        return newFA;
    }

    /**
     * Collects all states from delta on the character. The method handles that
     * a state med be created on basis of other states and if this is true the
     * basis states are used for collecting the states.
     *
     * @param state The from state
     * @param c The character used for calculating delta
     * @param stateAndOrigin the state may exist in this map. If exists in map
     *            each of the states from values must be used for finding the
     *            result.
     * @return all delta states on this character
     */
    private Set<State> collectStatesFromDelta(State state, char c, Map<State, Set<State>> stateAndOrigin) {
        Set<State> result = new HashSet<State>();

        if (stateAndOrigin.containsKey(state)) {
            // State is defined in the map key=state, value=Set<state>
            Set<State> originStates = stateAndOrigin.get(state);
            for (State s : originStates) {
                result.addAll(delta(s, c));
            }

        } else {
            result.addAll(delta(state, c));
        }

        return result;
    }
}
